package 力扣.栈;

import com.sun.corba.se.spi.presentation.rmi.IDLNameTranslator;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/*
【题目】一个整数数组 A，找到每个元素：右边第一个比我小的下标位置，没有则用 -1 表示。

        输入：[5, 2]
        输出：[1, -1]
* */
public class 找出数组中右边比我小的元素 {
    public static void main(String[] args) {
        int[] ints = {1,2,5,2,1,1,10};//[-1, 4, 3, 4, -1, -1, -1]
        int[] rightSmall = findRightSmall4(ints);
        System.out.println(Arrays.toString(rightSmall));
    }

    /** 数组中第一个比我小的元素 单调（递增）栈
       A[i]和其前面一个元素A[i-1]两个元素进行比较有两种情况：
        1、A[i] < A[i-1] 则说明找到了A[i-1]的右边第一个它小的元素
        2、A[i] >= A[i-1] 则说明没有找到了，需要遍历A[i+1] 重复进行上述的比较
     */
    public static int[] findRightSmall(int[] A){
        Deque<Integer> res = new LinkedList<>();
        for (int i = 0; i < A.length; i++) {
            int te = A[i];
            while (!res.isEmpty() && te < A[res.peek()]){
                A[res.pop()] = i;
            }
            res.push(i);
        }
        while (!res.isEmpty()){
            A[res.pop()] = -1;
        }
        return A;
    }

    //简约版

    /** 数组中第一个比我大的元素  单调（递减）栈
     只需一次循环，循环结束时不用在判断栈中是否还有元素
     */
    public static int[] findRightSmall2(int[] A){
        Deque<Integer> res = new LinkedList<>();
        int len = A.length;
        int[] ans = new int[len];
        for (int i = len - 1; i >= 0; i--) {//寻找右边第一个比我小的元素
            int te = A[i];
            while (!res.isEmpty() && A[res.peek()] >= te){//递减栈
                res.pop();
            }
            if (!res.isEmpty()){
                ans[i] = res.peek();
            }else {
                ans[i] = -1;
            }
            res.push(i);
        }
        return ans;
    }
    public static int[] findRightSmall4(int[] A){
         Deque<Integer> stack = new LinkedList<>();
         int[] ans = new int[A.length];
         for (int i = A.length - 1; i >= 0 ; i--) {
            while (!stack.isEmpty() && A[stack.peek()] <= A[i]){//递减栈  ‘>=’：表示数组右边第一个比我大的元素
                stack.poll();
            }
            if (!stack.isEmpty()){
                ans[i] = stack.peek();
            }else {
                ans[i] = -1;
            }
            stack.push(i);
        }
        return ans;
    }

}
